题目地址

• 🙂 第一次练习 2020-11-18
• 😄 第二次练习

解题方法

时间复杂度: O(n^2)
空间复杂度: O(n)

解题代码

class Solution {
       public int canCompleteCircuit(int[] gas, int[] cost) {
        int[] tmp = new int[gas.length];
        int count = 0;

        for (int i = 0; i < gas.length; i++) {
            int a = gas[i] - cost[i];
            tmp[i] = a;
            count += a;
        }

        if (count < 0)
            return -1;

        for (int i = 0; i < tmp.length; i++) {
            if (tmp[i] < 0) {
                continue;
            }
            int sum = 0;
            for (int j = i; j < i + tmp.length; j++) {
                sum = sum + tmp[j > tmp.length - 1 ? j % tmp.length : j];
                if (sum < 0) {
                    break;
                }

                if ((j > tmp.length - 1 ? j - tmp.length : j) == (i == 0 ? tmp.length - 1 : i - 1)) {
                    return i;
                }
            }
        }
        return -1;
    }
}